MSDS688 - Artifical Intelligence¶

Week 4 - Constraint Satisfaction Problems¶

In [3]:
Image('images/medieval_hydraulic_engineering.jpg')
Out[3]:

French King Henri IV hired the Italian engineer Tomaso Francini to build him some waterworks for the royal palace at Saint Germain en Laye. Francini built hydraulic grottoes devoted to the Greek pantheon and their adventures: Mercury played a trumpet and Orpheus his lyre; Perseus freed Andromeda from her dragon. There were automaton blacksmiths, weavers, millers, carpenters, knife-grinders, fishermen, and farriers conducting the obligatory watery attacks on spectators.

Cite: Riskin, J. (n.d.). Frolicsome Engines: The Long Prehistory of Artificial Intelligence. Retrieved April 10, 2018, from https://publicdomainreview.org/2016/05/04/frolicsome-engines-the-long-prehistory-of-artificial-intelligence/

Concise Review of Adversarial Search¶

Minimax¶

  • Based on DFS
  • Searches to constant depth
  • Evaluates each board at that depth
  • Number of evaluated nodes grows exponentially
    • b == branching factor with one branch per action
    • m == depth
    • Number of evaluated nodes = b^m
  • MIN and MAX must take what the other gives

Minimax Example¶

In [3]:
Image('images/Figure-S5-2-minmax-tree-example.png')
Out[3]:

Alpha-Beta¶

  • Alpha-Beta is layered on top of minimax

  • Remember that minimax search is depth-first

  • Only consider nodes along a single path

  • Alpha–beta pruning uses two parameters describing the bounds on backed-up values found along the path:

    • α = highest-value found so far for MAX along path.

    • β = lowest-value found so far for MIN along path.

  • Once a better play has been found, prune all other branches as high in the tree as possible.

Alpha-Beta Example¶

In [4]:
Image('images/Figure-S5-5-alphpabeta-pruning-example.png')
Out[4]:

Tonight¶

Tonight we are going to learn how to use constraint to make solutions easy to find. Apply this to coloring maps and scheduling talks.

Knowledge representation - Say HELLO to factored representations¶

  • Atomic representations is what we have used in our study of search

  • Factored representation

    • Splits up each state into a fixed set of variables or attributes, each of which can have a value

    • Commonly used in machine learning tasks

In [5]:
Image('images/Figure-S2-16-state-representations.png')
Out[5]:

Constraint satisfacation problems¶

  • General problem solving technique
  • Set of variables that can take on values
  • Set of values each variable can assume
  • Constriants limit values of local variables can assume
  • Solutions must satisfy all constraints (equal, _notequal, ...)
  • Resulting in a radical reduction in the size of the search space

Example: Map coloring¶

  • Coloring a map so that no adjacent polygons are the same color
  • Domain - {Red, Green, Blue}
  • Variable - Colorado
  • Constraint - Not equal to adjacent state
  • Graph theory
    • Planar graph can always be colored using just 4 colors
    • A planar graph has no crossing edges
In [6]:
Image('images/usa-states-map.png')
Out[6]:

Cite: http://www.conceptdraw.com/How-To-Guide/geo-map-america-united-states

How do we represent a map as a graph?¶

In [7]:
Image('images/Figure-S6-1-graph-coloring.png')
Out[7]:

¶

  • CSP
    • Variables: Q, NSW, V, T, SA, NT, WA
    • Domains: {Green, Yellow, Purple}
    • Constraints: No adjacent territory can be the same color

Map Coloring Exercise¶

  • Can you color Australia with just 3 colors?

  • Google aima-javascript

  • Click on View the Visualizations > Go to Part 2 > Chapter 6 Constraint Satisfation Problems

  • Or, just go to AIMA Visualizations - Constrain Satisfaction

In [8]:
Image('images/map-coloring-solution.png')
Out[8]:

Example: Scheduling¶

  • Domain - Time range

  • Variable - Start time, end time

  • Constraint - Start_Time_2 > Start_Time_1 + Duration_1

Solving CSPs with Search¶

Depth First Search (DFS)¶

  • Chooses values from domain
  • Assigns values choosen to variable
  • Checks for contradictions
  • Bactracks when a contradition is found
  • Not guaranteed to find a solution
In [9]:
Image('./images/time-travelers-convention_order_for_slides.png')
Out[9]:

DFS + Forward Checking (FC)¶

  • Idea: Look ahead and prune domains of unassigned variables

  • After assignment eliminate incompatible values from neighbors domains

  • Re-instate values when backtracking

Solution¶

In [4]:
Image('./images/time-traverlers-dfs-solution.jpg')
Out[4]:
In [10]:
Image('./images/time-travelers-convention_order_for_slides.png')
Out[10]:

DFS + FC + Propagation through singleton domains¶

  • Perform DFS + FC

  • If a new singleton domains are created propagate through the singleton's neighbors

  • Propigate == Remove inconsistent values from neighbors

  • Repeat if any new singletons result, propagate through them too

In [11]:
Image('./images/time-travelers-convention_order_for_slides.png')
Out[11]:

Break¶

Simplifying Search by Pre-Processing¶

  • Start on the node with the smallest domain
  • Remove any domain elements from adjacent domains for which there is no solution to the constraint
  • Repeat this process until all constraints are consistent in both directions

Arc Consistency¶

  • Remove domain elements that violate constraints(inconsistent)
  • Search is simplified and more efficient

Example¶

In [12]:
Image('images/arc-consistency-graph.png')
Out[12]:

Issue: Search repeatedly evaluates inconsistent domains¶

In [13]:
Image('images/arc-consistency-tree.png')
Out[13]:

Preprocessing¶

Idea: Eliminate conflicting domain values before search

AC-3 Algorithm¶

function AC-3(csp) returns false if an inconsistency is found and true otherwise

 inputs: csp, a binary CSP with components (X, D, C)

 local variables: queue, a queue of arcs, initially all the arcs in csp

 while queue is not empty do
   (Xi, Xj) ← REMOVE-FIRST(queue)

   if REVISE(csp, Xi, Xj) then
     if size of Di = 0 then return false
     for each Xk in Xi.NEIGHBORS − {Xj} do
      add(Xk, Xi) to queue
 return true

function REVISE(csp, Xi, Xj) returns true iff we revise the domain of Xi
 revised ← false
 for each x in Di do
   if no value y in Dj allows (x, y) to satisfy the constraint between Xi and Xj then
    delete x from Di
    revised ← true
 return revised

Practice exercise using AC-3¶

  • AC-3 is a preprocessing step to reduce the search space prior to search
In [14]:
Image('images/arc-consistency-graph.png')
Out[14]:

Summary¶

  • Use search to find solutions to constraint satisfaction problems (CSP)
  • Search finds solutions by making assignments
  • Pre-process domains to remove inconsistent domain values
  • Eliminate CSPs with no solution
  • Pre-processing makes search more effective
In [15]:
Image('https://imgs.xkcd.com/comics/python_environment.png')
Out[15]: